package leetcode.LinkedList;

import java.util.LinkedList;
import java.util.List;

/**
 * @author wangmaolin1
 * @date 2023/11/6 12:17
 */
public class _216 {
    static List<List<Integer>> res = new LinkedList<>();
    static int sum = 0;
    static LinkedList<Integer> childRes = new LinkedList<>();
    public static List<List<Integer>> combinationSum3(int k, int n) {
        backTrack(1, k, n);

        return res;
    }

    public static void backTrack(int start, int k, int target) {
        if (childRes.size() == k && sum == target) {
            res.add(new LinkedList<>(childRes));
            return;
        }
        if (childRes.size() >= k || sum > target) {
            return;
        }
        for (int i = start; i <= 9; i++) {
            if (childRes.size() >=k){
                continue;
            }
            childRes.add(i);
            sum += i;
            backTrack(i + 1, k, target);
            sum -= i;
            childRes.removeLast();
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum3(3, 7);
        System.out.println(lists);
    }
}
